This invention relates to decoding of signals encoded in a variable length code.
Variable length (VL) coding, such as Huffman coding, is a well known technique that encodes very likely signals with a small number of bits, and less likely signals with a larger number of bits. With this technique, the number of bits used to describe the less likely signals is larger than the number of bits in words of a corresponding fixed-length coding arrangement. The latter is a consequence of the inviolate requirement that one valid code cannot be a prefix of another valid code. In a trie structure representation, this requirement also corresponds to the statement that a node of the trie cannot also be a leaf of the trie.
Two tasks are involved in decoding a stream of bits that correspond to concatenated VL codes (VLCs): identifying the groups of bits that form valid VL codes; and decoding the valid VL codes.
FIG. 1 depicts a prior art arrangement for decoding such a stream. In the decoding process, data appears at a constant rate at line 41 and it is stored in buffer 40 as it is received. Data is extracted from buffer 40 and placed in register 10 under control of line 21, each time fully populating the register. The length of register 10 is equal to the maximum number of bits that a valid VL code can have. The data stored in register 10 is applied to combinatorial circuit 20 which, in each decoding interval, identifies the subset of bits in the data (starting with the oldest bits in register 10) that forms a valid VL code. Circuit 20 outputs on bus 21 the fixed-length code that corresponds to the identified subset of bits that form the VL code, and outputs a control signal on bus 21. Control signal 21 directs buffer 40 to supply a number of new bits to register 10 (for the next decoding interval) to replace the bits in the identified VL code. Thus, buffer 40 serves merely as a signal rate buffer means, allowing the output to operate at the rate corresponding to the rate at which the fixed-length codes were originally converted to the variable length codes, while the input arrives at the bit rate of the variable length codes.
The simplest way to implement circuit 20 is with a look-up table (e.g., a read-only-memory). A read only memory also requires the shortest processing time. The problem with this prior art approach, however, is the size of the memory that is required, which is 2.sup.M, where M is the number of bits in the longest VL code. For many practical applications, such as for high definition TV (HDTV), M is quite large, perhaps larger than 20, and that makes ROM 20 prohibitively large.